package com.linyaonan.leetcode.easy._1170;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。
 * <p>
 * 例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。
 * <p>
 * 现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：queries = ["cbd"], words = ["zaaaz"]
 * 输出：[1]
 * 解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
 * 示例 2：
 * <p>
 * 输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
 * 输出：[1,2]
 * 解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= queries.length <= 2000
 * 1 <= words.length <= 2000
 * 1 <= queries[i].length, words[i].length <= 10
 * queries[i][j], words[i][j] 都是小写英文字母
 *
 * @author: Lin
 * @date: 2020/1/12
 */
public class CompareStrings {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        List<Integer> result = new ArrayList<>();
        int[] qInt = new int[queries.length];
        int[] wInt = new int[words.length];
        for (int i = 0; i < queries.length; i++) {
            qInt[i] = getCharMinCount(queries[i]);
        }
        for (int i = 0; i < words.length; i++) {
            wInt[i] = getCharMinCount(words[i]);
        }
        Arrays.sort(wInt);
        for (int i = 0; i < qInt.length; i++) {
            int count = 0;
            for (int j = wInt.length - 1; j >= 0; j--) {
                if (wInt[j] > qInt[i]) {
                    count++;
                } else {
                    break;
                }
            }
            result.add(count);
        }
        int[] r = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            r[i] = result.get(i);
        }
        return r;

    }

    private int getCharMinCount(String q) {
        if (q == null || "".equals(q)) {
            return 0;
        }
        int[] t = new int[26];
        for (char c : q.toCharArray()) {
            t[c - 'a']++;
        }
        for (int i : t) {
            if (i != 0) {
                return i;
            }
        }
        return 0;
    }
}
